In modern communication systems based on data packet transmission, such as the Internet, millions of data packets per second are forwarded in each switching node from the input to one of several output links, depending on the address information contained in the data packet header. The association between data packet address and output link (or route) is stored in a routing table of the switching node, and for each data packet a lookup or search operation is made in this table for obtaining the routing information, also referred to as output link identification. This lookup may cause delays if resources are limited. As many data packets—such as periodic data packets of voice streams, or bursts of data packets for file transfers—contain the same address, one has used cache memories for storing each addresses when it first occurred and the respective associated output or routing information once it has been found by a lookup operation. This avoids many recurring lookup searches for the same address, but requires large sizes of cache memories. However, due to the finite size of any cache memory, storage locations have to be cleared for new cache entries once the cache is filled up. Often, an LRU (least recently used) algorithm is used for this task, thus eliminating cache entries which obviously were not used for some time.
However, when the cache memory management employs an LRU algorithm, and when the communication system has to transfer a great number of data packets for traffic of periodic nature such as voice or video transmissions, many intervening data packets will occur between consecutive data packets of the same periodic transmission, so that most cache entries would have been eliminated before they can be used again. This is of course very ineffective. Furthermore, some traffic categories should be handled with higher priority than others. Thus, some kind of optimization or improvement is required for the cache entry procedure to avoid the handling effort and the waste of cache space for cache entries which will be used rarely or only once anyway.
The usage of cache memories in routers of IP data packet forwarding systems has been discussed in the following publication: Peter Newman et al.: “IP Switching and Gigabit Routers”, IEEE Communications Magazine, Vol. 35, No. 1 (January 1997), pp. 64–69. The result of this investigation was that caching for high-speed links at 1 Gbit/s and above will not be useful due to the lack of locality in addresses. Another approach discussed in this paper which deals with a particular (Ipsilon) IP switching system is conceptually different in that it suggests to forward connection-less IP traffic over a connection-oriented ATM traffic infrastructure.
Classification of data packets in IP switching nodes in response to the contents of their headers was discussed in T. V. Lakshman, D. Stiliadis: “High-speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching”, Proc. ACM SIGCOMM'98, Comp. Commun. Rev. Vol. 28, No. 4, October 1998, pp. 203–214 and also in P. Gupta, N. McKeown: “Packet Classification on Multiple Fields”, ACM SIGCOMM'99, Comp. Commun. Rev. Vol. 29, No. 4, Ovt. 1999, pp. 147–160.
In none of these publications, procedures were suggested for connection-less data packet transmission systems to select, in response to the evaluation of data packet headers, certain flows or traffic categories for entry into a cache memory, to avoid later lookup operations for data packets of the same flow or traffic category, but to avoid on the other hand useless cache entries into the cache.